// Heapsort.cpp : 定义控制台应用程序的入口点。
//
 
#include<iostream>
using namespace std;
void adjustHeap(int arr[], int i, int length)		//调整大顶堆（仅是调整过程，建立在大顶堆已构建的基础上）
{
	int bigest = i ;
    int left =2*i + 1;
    int right =2*i + 2;
    if(left < length && arr[bigest] < arr[left])
    {
        bigest = left;
    }
    if(right < length && arr[bigest] < arr[right])
    {
		bigest = right;
    }
    if(bigest != i)
    {
        //这里可以知道我影响了此时i位置的树
		swap(arr[i],arr[bigest]);
        adjustHeap(arr,bigest,length);//然后递归调用
    }
}
void Heapsort(int arr[], int length)
{
	//1.构建大顶堆
	for (int i = length / 2 - 1; i >= 0; i--)
	{
		//从第一个非叶子结点从下至上，从右至左调整结构
		adjustHeap(arr, i, length);
	}
	for (int j = length - 1; j>0; j--)
	{
		swap(arr[0], arr[j]);//将堆顶元素与末尾元素进行交换
		adjustHeap(arr, 0, j);//重新对堆进行调整
	}
 
}
int main()
{
	int arr[9] = { 9,8,7,6,10,4,3,2,1 };
	Heapsort(arr, 9);
	for (int i = 0; i<9; i++)
		cout << arr[i] << " ";
	cout << endl;
	return 0;
}
 